package 题目集.动态规划;

import org.junit.Test;

import java.util.Arrays;

/**
 * todo：未完成 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符 '*'
 * 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * https://leetcode.cn/problems/regular-expression-matching/
 *
 * 当前为*时
 */
public class 正则表达式匹配 {

	static char[] s;
	static char[] p;
	int[][] dp;

	public boolean isMatch(String str, String pattern) {
		s = str.toCharArray();
		p = pattern.toCharArray();
		dp = new int[s.length + 1][p.length + 1];
		return dfs(0, 0);
	}

	public boolean dfs(int i, int j) {
		if (i == s.length) {
			boolean cur;
			if (j == p.length) {
				cur = true;
			} else {
				cur = j + 1 < p.length && p[j + 1] == '*' && dfs(i, j + 2);
			}
			dp[i][j] = cur ? 1 : 2;
		} else if (j == p.length) {
			dp[i][j] = 2;
		}
		if (dp[i][j] != 0)
			return dp[i][j] == 1;

		if (j + 1 < p.length && p[j + 1] == '*')
			return dfs(i, j + 1);
		if (p[j] != '*') {
			dp[i][j] = match(i, j) && dfs(i + 1, j + 1) ? 1 : 2;
		} else if (!match(i, j - 1)) {
			dp[i][j] = dfs(i, j + 1) ? 1 : 2;
		} else {
			boolean chose0 = false, chose1 = false, choseN = false;
			chose0 = dfs(i, j + 1);
			chose1 = dfs(i + 1, j + 1);
			choseN = dfs(i + 1, j);
			dp[i][j] = chose0||chose1 || choseN ? 1 : 2;
		}
		return dp[i][j] == 1;
	}

	public boolean match(int i, int j) {
		if (s[i] == p[j])
			return true;
		return p[j] == '.';
	}

	@Test
	public void test() {
		System.out.println(isMatch("bbbba", ".*a*a"));
	}
}
